/**
 * @Author Fizz Pu
 * @Date 2020/9/13 下午7:30
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
 *
 * 两个相邻元素间的距离为 1 。
 */

// 思考：这道提很明显可以用bfs解决
// 第二个问题就是重复搜索问题，如果以每个元素为起点，执行bfs搜索，那的话空间复杂度太高了

// 这道题有个处理得不好的地方，就是可能会重复搜索，改进是队列存储行和列的数组
// 二是可以先把所有的0入队，开始搜索bfs搜索
// 题解    https://leetcode-cn.com/problems/01-matrix/solution/tao-lu-da-jie-mi-gao-dong-ti-mu-kao-cha-shi-yao-2/
// 写算法尽量要快，不必太在意设计
public class Lee54201 {
    public static void main(String[] args) {
        int[][] matrix = {
                {0, 0, 0},
                {0, 1, 0},
                {0, 1, 0},
                {0, 1, 0},
                {0, 1, 0}
        };
        int[][] res = new Lee54201().updateMatrix(matrix);
        for(int i = 0; i < matrix.length; ++i){
            for(int j = 0; j < matrix[0].length; ++j){
                System.out.print(res[i][j] + ", ");
            }
            System.out.println();
        }
    }

    public int[][] updateMatrix(int[][] matrix) {
        int[][] copy = new int[matrix.length][matrix[0].length];

        for(int i = 0; i < matrix.length; ++i){
            for(int j = 0; j < matrix[0].length; ++j){
                bfs(matrix,copy, i, j);
            }
        }
        return copy;
    }

    private void bfs(int[][] matrix, int[][] res, int row, int col){
        Deque<Node> queue = new LinkedList<>();
        Node start = new Node(matrix, row, col);
        queue.add(start);
        int distance = 0;
        while (!queue.isEmpty()){
            // 当前层的元素全部出栈
            int size = queue.size();
            for(int i = 0; i < size; ++i){
                Node element = queue.remove();
                if(element.isZero()){
                    res[row][col] = distance;
                    return;
                }
                //获得element的周围的元素
                // 之前的逻辑设计有问题
                Node down, up, right, left;
                if((down = element.getDown(matrix.length-1)) != null){
                    queue.add(down);
                }if((up = element.getUp(0)) != null){
                    queue.add(up);
                }if((left = element.getLeft(0)) != null){
                    queue.add(left);
                }if((right = element.getRight(matrix[0].length-1)) != null){
                    queue.add(right);
                }
            }
            ++distance;
        }
    }

}

class Node{
    public static int[][] matrix;
    private int val;
    private int row;
    private int col;
    public Node(int[][] matrix, int row, int col){
        Node.matrix = matrix;
        this.val = matrix[row][col];
        this.row = row;
        this.col = col;
    }

    public boolean isZero(){
        return val == 0;
    }

    // right 为右边界
    public Node getRight(int right){
        return col + 1 <= right ? new Node(matrix, row, col+1) : null;
    }

    public Node getLeft(int left){
        return col - 1 < left ? null : new Node(matrix, row, col-1);
    }

    public Node getUp(int up){
        return row - 1 < up ? null :new Node(matrix, row-1, col) ;
    }

    public Node getDown(int down){
        return row + 1 <= down ? new Node(matrix, row + 1, col) : null;
    }
}